perm filename V2N.IN[TEX,DEK] blob
sn#285514 filedate 1977-05-29 generic text, type C, neo UTF8
COMMENT ⊗ VALID 00008 PAGES
C REC PAGE DESCRIPTION
C00001 00001
C00002 00002 folio 621 galley 1
C00020 00003 folio 624 galley 2
C00040 00004 folio 629 galley 3
C00054 00005 folio 632 galley 4
C00070 00006 folio 635 galley 5
C00085 00007 folio 638 galley 6
C00097 00008 folio 643 galley 7
C00114 ENDMK
C⊗;
folio 621 galley 1
0 {U0}{H10L12M29}58320#Computer Programming!(A.-W./Knuth)!ch.
2 4!f. 621!g. 1D|'{A12}|π!|4|4|4|4An even better
8 scheme for large |εn, |πdiscovered by Volker
15 Strassen in 1968, is based on the fact that the
25 product of 2|4α⊗↓|42 matrices can be evaluated
32 with only 7 multiplications, without relying
38 on the commutativity of multiplication as in
45 (35). Therefore 2|εn|4α⊗↓|42n |πmatrices can
50 be partitioned into four |εn|4α⊗↓|4n |πmatrices
56 and the idea can be used recursively to obtain
65 the product of |ε2|gk|4α⊗↓|42|gk |πmatrices with
71 only 7|ε|gk |πmultiplications instead of |ε(2|gk)|g3|4α=↓|48
76 |gk. |πStrassen's original 2|4α⊗↓|42 identity
81 |ε[Numer. Math. |≡1|≡3 (1969), 354<356] |πused
87 7 multiplications and 18 additions; S. Winograd
94 later discovered the following more economical
100 formula:|'{A6}|h|ε|9|1|1a!b|9|1|1|9|1|1A!D|9|1|1|4α=↓|4|9|1|
101 1|∂w|4α+↓|4(a|4α_↓|4c)(D|4α_↓|4C)|4α_↓|4d(A|4α_↓|4B|4α_↓|4C|
101 4α+↓|4D)!!|∂kplolhjk.,|E|n|'|↔|(a!b|d5c!d|)|↔s|↔a|(A!C|d5B!D
102 |)|↔s|4α=↓|4|↔a|'{B26}|LaA|4α+↓|4bB|Lw|4α+↓|4(c|4α+↓|4d)(C|4
103 α_↓|4A)|4α+↓|4(a|4α+↓|4b|4α_↓|4c|4α_↓|4d)D>{A2}|Lw|4α+↓|4(a|
104 4α_↓|4c)(D|4α_↓|4C)|4α_↓|4d(A|4α_↓|4B|4α_↓|4C|4α+↓|4D)|Lw|4α
104 +↓|4(a|4α_↓|4c)(D|4α_↓|4C)|4α+↓|4(c|4α+↓|4d)(C|4α_↓|4A)>
105 {A4}(36)|?{A6}|πwhere |εw|4α=↓|4aA|4α_↓|4(a|4α_↓|4c|4α_↓|4d)
107 (A|4α_↓|4C|4α+↓|4D). |πIf intermediate results
111 are appropriately saved, (36) involves 7 multiplications
118 and only 15 additions; by induction on |εk, |πwe
127 can multiply |ε2|gk|4α⊗↓|42|gk |πmatrices with
132 |ε7|gk |πmatrices with |ε7|gk |πmultiplications
137 and |ε5(7|gk|4α_↓|44|gk) |πadditions. The total
142 number of operations needed to multiply |εn|4α⊗↓|4n
149 |πmatrices has therefore been reduced from order
156 |εn|g3 |πto |εO(n|π|gl|gg|1|1|g7)|4α=↓|4|εO(n|g2|g.|g8|g0|g7
158 |g4). |πStrassen showed that |εA |πsimilar reduction
165 applies also to the evaluation of determinants
172 and matrix inverses; cf. J. R. Bunch and J. E.
182 Hopcroft, |εMath. Comp. |≡2|≡8 (1974), 231<236.|'
188 |π!|4|4|4|4These theoretical results are quite
193 striking, but from a practical standpoint they
200 are of limited use because |εn |πmust be very
209 large before we overcome the e=ect of additional
217 bookkeeping costs. Richard Brent [Stanford Computer
223 Science report CS157 (March, 1970), see also
230 |εNumer. Math. |≡1|≡6 (1970), 145<156] |πfound
236 that a careful implementation of Winograd's scheme
243 (35), with appropriate scaling for numerical
249 stability, became better than the conventional
255 scheme only when |εn|4|¬R|440, |πand it saved
262 7 percent of the running time when |εn|4α=↓|4100.
270 |πFor complex arithmetic the situation was somewhat
277 di=erent; (35) became advantageous for |εn|4|¬Q|420,
283 |πand saved 18 percent when |εn|4α=↓|4100. |πHe
290 estimated that Strassen's scheme would not begin
297 to excel more than 60,000 entries, rarely occur
305 in practice (unless they are very sparse, when
313 other techniques apply).|'!|4|4|4|4By contrast,
318 the methods we shall discuss next are eminently
326 practical nd have found wide use. The |ε⊂nite
334 Fourier transform f |πof a complex-valued function
341 |εF |πof |εn |πvariables, over domains of |εm|β1,|4.|4.|4.|4
348 ,|4m|βn |πelements, is de_ned by the equation|'
355 {A6}|εf|1(s|β1,|4.|4.|4.|4,|4s|βn)|4α=↓|4|↔k|uc|)0|¬Et|β1|¬W
355 m|β1|d.|4.|4.|4.|4.|4|d0|¬Et|βn|¬Wm|βn|)|4|πexp|↔a2|≤pi|↔a|(
355 s|β1t|β1|d2m|β1|)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4|(s|βnt|βn|d
355 2m|βn|)|↔s|↔sF(t|β1,|4.|4.|4.|4,|4t|βn)|J!(37)|;
356 {A6}|πfor |εo|4|¬E|4s|β1|4|¬W|4m|β1,|4.|4.|4.|4,|40|4|¬E|4s|
357 βn|4|¬W|4m|βn; |πthe name ``transform'' is justi_ed
363 because we can recover the values |εF(t|β1,|4.|4.|4.|4,|4t|β
369 n) |πfrom the values |εf|1(s|β1,|4.|4.|4.|4,|4s|βn),
374 |πas shown in exercise 13. In the important special
383 case that all |εm|βj|4α=↓|42, |πwe have|'{A6}|εf|1(s|β1,|4.|
389 4.|4.|4,|4s|βn)|4α=↓|4|↔k|uc|)0|¬Et|β1,|4.|4.|4.|4,|4t|βn|¬E
389 1|)|4(|→α_↓1)|urs|β1t|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4s|βnt
389 |βn|)|)F(t|β1,|4.|4.|4.|4,|4t|βn)|J!(38)|;{A6}|πfor
391 |ε0|4|¬E|4s|β1,|4.|4.|4.|4,|4s|βn|4|¬E|41, |πand
393 this may be regarded as a simultaneous evaluation
401 of |ε2|gn |πlinear polynomials in 2|ε|gn |πvariables
408 |εF(t|β1,|4.|4.|4.|4,|4t|βn). |πA well-known
411 technique due to F. Yates |εThe Design and Analysis
420 of Factorial Experiments (|πHarpenden: Imperial
425 Bureau of Soil Sciences, 1937)] can be used to
434 reduce the number of additions implied in (38)
442 from |ε2|gn(2|gn|4α_↓|41) |πto |εn2|gn. |πYate's
447 method can be understood by considering the case
455 |εn|4α=↓|43: |πLet |εx|ur|)t|β1t|β2t|β3|)|4α=↓|4F(t|β1,|4t|β
457 2,|4t|β3).|'{A6}{H6L7M29}|h|ε|∂x|β2|β2|β2!!|∂x|β1|β1|β1|4α⊗↓
458 |4x|β1|β1|β1!!|∂x|β2|β2|β2|4α⊗↓|4x|β0|β0|β0|4α⊗↓|4x|β0|β0|β9
458 |4α⊗↓|4x|β0|β0|β0!!|∂x|β0|β0|β0|4α⊗↓|4x|β0|β0|β0|4α⊗↓|4x|β0|
458 β0|β0|4α=↓|4x|β0|β0|β0|4α⊗↓|4x|β0|β0|β0|4α=↓|4x|β0|β0|β0|4α=
458 ↓|4x|β0|β0|β0|4α⊗↓|4x|β0|β0|β0|∂|E|n|'|>|πGiven|'
461 First|4step!!|;Second|4step!!|;Third|4step|;>
465 {A2}|εx|β0|β0|β0!!x|β0|β0|β0|4α+↓|4x|β0|β0|β1!!x|β0|β0|β0|4α
465 +↓|4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1!!x|β0|β0|β0
465 |4α+↓|4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α+↓|4x|
465 β1|β0|β0|4α+↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|
465 'x|β0|β0|β1!!x|β0|β1|β0|4α+↓|4x|β0|β1|β1!!x|β1|β0|β0|4α+↓|4x
466 |β1|β0|β1|4α+↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓
466 |4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α+↓|4x|β1|β0
466 |β0|4α_↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
467 x|β0|β1|β0!!x|β1|β0|β0|4α+↓|4x|β1|β0|β1!!x|β0|β0|β0|4α_↓|4x|
467 β0|β0|β1|4α+↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1!!x|β0|β0|β0|4α+↓|
467 4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α+↓|4x|β1|β0|
467 β0|4α+↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
468 x|β0|β1|β1!!x|β1|β1|β0|4α+↓|4x|β1|β1|β1!!x|β1|β0|β0|4α_↓|4x|
468 β1|β0|β1|4α+↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓|
468 4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α+↓|4x|β1|β0|
468 β0|4α_↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|'
469 x|β1|β0|β0!!x|β0|β0|β0|4α_↓|4x|β0|β0|β1!!x|β0|β0|β0|4α+↓|4x|
469 β0|β0|β1|4α_↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1!!x|β0|β0|β0|4α+↓|
469 4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
469 β0|4α_↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
470 x|β1|β0|β1!!x|β0|β1|β0|4α_↓|4x|β0|β1|β1!!x|β1|β0|β0|4α+↓|4x|
470 β1|β0|β1|4α_↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓|
470 4x|β0|β0|β1|4α+↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
470 β0|4α+↓|4x|β1|β0|β1|4α_↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|'
471 x|β1|β1|β0!!x|β1|β0|β0|4α_↓|4x|β1|β0|β1!!x|β0|β0|β0|4α_↓|4x|
471 β0|β0|β1|4α_↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1!!x|β0|β0|β0|4α+↓|
471 4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α_↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
471 β0|4α_↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1|'
472 x|β1|β1|β1!!x|β1|β1|β0|4α_↓|4x|β1|β1|β1!!x|β1|β0|β0|4α_↓|4x|
472 β1|β0|β1|4α_↓|4x|β1|β1|β0|4α+↓|4x|β1|β1|β1!!x|β0|β0|β0|4α_↓|
472 4x|β0|β0|β1|4α_↓|4x|β0|β1|β0|4α+↓|4x|β0|β1|β1|4α_↓|4x|β1|β0|
472 β0|4α+↓|4x|β1|β0|β1|4α+↓|4x|β1|β1|β0|4α_↓|4x|β1|β1|β1|'
473 {A6}{H10L12M29}|πTo get from the ``Given'' to
479 the ``First step'' requires four additions and
486 four subtractions; and the interesting feature
492 of Yates's method is that exactly the same transformation
501 which takes us from ``Given'' to ``First step''
509 will take us from ``First step'' to ``Second
517 step'' and from ``Second step'' to ``Third step.''
525 In each case we do four additions, then four
534 subtractions; and after three steps we have the
542 desired Fourier transform |εf|1(s|β1, s|β2, s|β3)
548 |πin the place originally occupied by |εF|1(s|β1,
555 s|β2, s|β3)*3|'|π!|4|4|4|4This special case is
561 often called the |εWalsh transform |πof 2|ε|gn
568 |πdata elements, since the corresponding pattern
574 of signs was studied by J. L. Walsh |ε[Amer.
583 J. Math. |≡4|≡5 (1923), 5<24]. |πNote that the
591 number of sign changes from left to right in
600 the ``Third step'' above assumes the respective
607 values 0, 7, 3, 4, 1, 6, 2, 5. Walsh observed
618 that there will be exactly 0, 1,|4.|4.|4.|4,|42|ε|gn|4α_↓|41
624 |πsign changes in some order in the general
633 case, so the coe∃cients provide discrete approximations
640 to sine waves with various frequencies. (See
647 H. F. Harmuth, |εIEEE Spectrum |≡6|≡, 11 (|πNov.
655 1969), 82<91 for applications of this property,
662 and see Section 7.2.1 for further discussion
669 of the Walsh coe∃cients.)|'!|4|4|4|4Yates's method
675 can be generalized to the evaluation of any _nite
684 Fourier transform, and, in fact, to the evaluation
692 of any sum which can be written|'{A6}|εf|1(s|β1,|4s|β2,|4.|4
699 .|4.|4,|4s|βn)|4α=↓|4|↔k|uc|)0|¬Et|β1|¬Wm|β1|d.|4.|4.|4.|4|d
699 0|¬Et|βn|¬Wm|βn|)|4g|β1(s|β1,|4s|β2,|4.|4.|4.|4,|4s|βn|4t|β1
699 )g|β2(s|β2,|4.|4.|4.|4,|4s|βn,|4t|β2)|4|¬O|4|¬O|4|¬O|'
700 {A4}g|βn(s|βn,|4t|βn)F(t|β1,|4t|β2,|4.|4.|4.|4,|4t|βn),|40|4
700 |¬E|4s|βj|4|¬W|4m|βj,!(29)|?{A6}|πfor given functions
704 |εg|βj(s|βj,|4.|4.|4.|4,|4s|βn,|4t|βj). |πProceed
706 as follows:|'{A6}|h|εf|g[|g2|g](s|βn|βα_↓|β1,|4s|βn,|4t|β1,|
708 4.|4.|4.|4,|4t|βn|βα_↓|β2|4|∂oikolp|E|n|'| f|g[|g0|g](t|β1,|
709 4t|β2,|4t|β3,|4.|4.|4.|4,|4t|βn)|4|Lα=↓|4F(t|β1,|4t|β2,|4t|β
709 3,|4.|4.|4.|4,|4t|βn);>{A6}| f|g[|g1|g](s|βn,|4t|β1,|4t|β2,|
710 4.|4.|4.|4,|4t|βn|βα_↓|β1)|4|Lα=↓|4|↔k|uc|)0|¬Et|βn|¬Wm|βn|)
710 |4g|βn(s|βn,|4t|βn)f|g[|g0|g](t|β1,|4t|β2,|4.|4.|4.|4,|4t|βn
710 );|'{A6}| f|g[|g2|g](s|βn|βα_↓|β1,|4s|βn,|4t|β1,|4.|4.|4.|4,
711 |4t|βn|βα_↓|β2)|4|Lα=↓|4|↔k|uc|)0|¬Et|βn|βα_↓|β1|¬Wm|βn|βα_↓
711 |β1|)|4g|βn|βα_↓|β1(s|βn|βα_↓|β1,|4s|βn,|4t|βn|βα_↓|β1)f|g[|
711 g1|g](s|βn,|4t|β1,|4.|4.|4.|4,|4t|βn|βα_↓|β1);|'
712 {A6}!|¬O|4|¬O|4|¬O|'| f|g[|gn|g](s|β1,|4s|β2,|4s|β3,|4.|4.|4
713 .|4,|4s|βn)|4|Lα=↓|4|↔k|uc|)0|¬Et|β1|¬Wm|β1|)|4g|β1(s|β1,|4.
713 |4.|4.|4,|4s|βn,|4t|β1)f|g[|gn|gα_↓|g1|g](s|β2,|4s|β3,|4.|4.
713 |4.|4,|4s|βn,|4t|β1);|'{A6}| | f|1(s|β1,|4s|β2,|4s|β3,|4.|4.
714 |4.|4,|4s|βn)|4|Lα=↓|4f|g[|gn|g](s|β1,|4s|β2,|4s|β3,|4.|4.|4
714 .|4,|4s|βn).|J!(40)>{A6}|Hβ*?{U0}{H10L12M29}58320#Computer
folio 624 galley 2
716 Programming!(A.-W./Knuth)!ch. 4!f. 624!g. 2D|'
720 {A12}|πFor Yate's method as shown above, |εg|βj(s|βj,|4.|4.|
726 4.|4,|4s|βn,|4t|βj)|4α=↓|4(α_↓1)|gs|rj|gt|rj;
727 f|g[|g0|g](t|β1,|4t|β2,|4t|β3) |πrepresents the
730 ``Given''; |εf|g[|g1|g](s|β3,|4t|β1,|4t|β2) |πrepresents
733 the ``First step''; etc. Whenever a sum can be
742 put into the form of (39), for reasonably simple
751 functions |εg|βj(s|βj,|4.|4.|4.|4,|4s|βn,|4t|βj),
753 |πthe scheme (40) will reduce the amount of computation
762 from order |εN|g2 |πto rougly the order |εN|4|πlog
770 |εN, |πwhere |εN|4α=↓|4m|β1,|4.|4.|4.|4m|βn;
773 |πfurthermore this scheme is ideally suited to
780 parallel computation. The important special case
786 of one-dimensional Fourier transforms is discussed
792 in exercise 14.|'!|4|4|4|4Let us consider one
799 more special case of polynomial evaluation. |εLagrange's
806 interpolation polynomial |πof order |εn, |πwhich
812 we shall write as|'{A6}|h|εu|g[|gn|g](x)|4|∂α=↓|4α+↓|4y|β1|4
816 (x|β1|4α_↓|4x|β0)(x|β1|4α+↓|4x|β2)|4.|4.|4.|4(x|β1|4α+↓|4x|β
816 n)|4α=↓|4.|4.|4.|E|n|;| u|g[|gn|g](x)|4|Lα=↓|4y|β0|4|((x|4α_
817 ↓|4x|β1)(x|4α_↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn)|d2(x|β
817 0|4α_↓|4x|β1)(x|β0|4α_↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|β0|4α_↓|4x
817 |βn)|)>{A4}|L|4|4|4|4|4|1|1α+↓|4y|β1|4|((x|4α_↓|4x|β0)(x|4α_
818 ↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn)|d2(x|β1|4α_↓|4x|β0)(
818 x|β1|4α_↓|4x|β2)|4|¬O|4|¬O|4|¬O|4(x|β1|4α_↓|4x|βn)|)|4α+↓|4|
818 ¬O|4|¬O|4|¬O>{A4}|L|4|4|4|4|1|1α+↓|4y|βn|4|((x|4α_↓|4x|β0)(x
819 |4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn|βα_↓|β1)|d2(x|βn|
819 4α_↓|4x|β0)(x|βn|4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|4(x|βn|4α_↓|4x|β
819 n|βα_↓|β1)|)|4,|J!(41)>{A6}|πis the only polynomial
824 of degree |ε|¬En |πin |εx |πwhich takes on the
833 respective values |εy|β0,|4y|β1,|4.|4.|4.|4,|4y|βn
836 |πat the |εn|4α+↓|41 |πdistinct points |εx|4α=↓|4x|β0,|4x|β1
841 ,|4.|4.|4.|4,x|βn. |π(For it is evident from
847 (41) that |εu|g[|gn|g](x|βk)|4α=↓|4y|βk |πfor
851 |ε0|4|¬E|4k|4|¬E|4n. |πIf |εf|1(x) |πis any such
857 polynomial of degree |ε|¬En, |πthen |εg(x)|4α=↓|4f|1(x)|4α_↓
862 |4u|g[|gn|g](x) |πis of degree |ε|¬En, |πand
868 |εg(x) |πis zero for |εx|4α=↓|4x|β0,|4x|β1,|4.|4.|4.|4,|4x|β
872 n; |πtherefore |εg(x) |πis a multiple of the
880 polynomial |ε(x|4α_↓|4x|β0)(x|4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|4(x
881 |4α_↓|4x|βn). |πThe degree of the latter polynomial
888 is greater than |εn, |πso |εg(x)|4α=↓|40.) |πIf
895 we assume that the values of a function in some
905 table are well-approximated by a polynomial,
911 Lagrange's formula (41) may there fore be used
919 to ``interpolate'' for values of the function
926 at points |εx |πnot appearing in the table. Unfortunately,
935 there seem to be quite a few additions, subtractions,
944 multiplications, and divisions in Lagrange's
949 formula; in fact, there are |εn |πadditions,
956 |ε2n|g2|4α+↓|42 |πsubtractions, |ε2n|g2|4α+↓|4n|4α_↓|41
959 |πmultiplications, and |εn|4α+↓|41 |πdivisions.
963 Fortunately (as we might suspect), improvement
969 is possible.|'|4|4|4|4!The basic idea for simplifying
976 (4) is to note that |εu|g[|gn|g](x)|4α_↓|4u|g[|gn|gα_↓|g1|g]
981 (x) |πis zero for |εx|4α=↓|4x|β0,|4.|4.|4.|4,|4x|βn|βα_↓|β1;
985 |πthus |εu|g[|gn|g](x)|4α_↓|4u|g[|gn|gα_↓|g1|g](x)
988 |πis a polynomial of degree |ε|¬En |πand a multiple
997 of |ε(x|4α_↓|4x|β0)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn|βα_↓|β1).
999 |πWe conclude that |εu|g[|gn|g](x)|4α=↓|4|≤a|βn(x|4α_↓|4x|β0
1002 )|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4x|βn|βα_↓|β1)|4α+↓|4u|g[|gn|gα_↓|
1002 g1|g](x), |πwhere |ε|≤a|βn |πis a constant. This
1009 leads us to |εNewton's interpolation formula{A6}u|g[|gn|g](x
1014 )|4α=↓|4|∂|≤a|βn(x|4α_↓|4x|β0)(x|4α_↓|4x|β1)|4|¬O|4|¬O|4|¬O|
1014 4(x|4α_↓|4x|βn|βα_↓|β1)|4α+↓|4|¬O|4|¬O|4|¬O|;
1015 {A4}|Lα+↓|4|≤a|β2(x|4α_↓|4x|β0)(x|4α_↓|4x|β1)|4α+↓|4|≤a|β1(x
1015 |4α_↓|4x|β0)|4α+↓|4|≤a|β0,|J!(42)>{A6}|πwhere
1017 the |ε|≤a'|πs are some constants we should like
1025 to determine from |εx|β0,|4x|β1,|4.|4.|4.|4,
1029 x|βn,|4y|β0,|4y|β1,|4.|4.|4.|4,|4y|βn. |πNote
1031 that this formula holds for all |εn; |≤a|βk |πdoes
1040 not depend on |εx|βk|βα+↓|β1,|4.|4.|4.|4,|4x|βn,|4y|βk|βα+↓|
1043 β1,|4.|4.|4.|4,|4y|βn. |πOnce the |ε|≤a'|πs are
1048 known, Newton's interpolation formula is conveneient
1054 for calculation, since we may generalize Horner's
1061 rule once again and write|'{A6}|εu|g[|gn|g](x)|4α=↓|4{H12}({
1066 H10}(|¬O|4|¬O|4|¬O|4(|≤a|βn(x|4α_↓|4x|βn|βα_↓|β1)|4α+↓|4|≤a|
1066 βn|βα_↓|β1)(x|4α_↓|4x|βn|βα_↓|β2)|4α+↓|1|1|¬O|4|¬O|4|¬O)(x|4
1066 α_↓|4x|β0)|4α+↓|4|≤a|β0{H12}){H10}.|;{A4}(43)|?
1068 {A6}|πThis requires |εn |πmultiplications and
1073 |ε2n |πadditions. Alternatively, we may evaluate
1079 eachof the individual terms of (42) from right
1087 to left; with |ε2n|4α_↓|41 |πmultiplications
1092 and |ε2n |πadditions we thereby calculate all
1099 of the values |εu|g[|g0|g](x), u|g[|g1|g](x),|4.|4.|4.|4,|4u
1103 |g[|gn|g](x), |πand this indicates whether or
1109 not the interpolation process is ``converging.''|'
1115 !|4|4|4|4The |ε|≤a'|πs in Newton's formula may
1121 be found by computing the ``divided di=erences''
1128 in the following tableau (shown for |εn|4α=↓|43):|'
1135 {A6}}h10l7}|h|ε|∂y|β0|9|∂(y|β2|4α_↓|4y|β1)/(x|β2|4α_↓|4x|β1)
1135 |4α+↓|4y|β2|9|∂(y|β2|4α_↓|4y|β1)/(x|β2|4α_↓|4x|β0)|4α=↓|4y|β
1135 2|9|∂(y|β3|4α_↓|4y|β3)/(x|β3|4α_↓|4x|β0)|4α=↓|4y|9|1|E|n|;
1136 |Ly|β0>|L|L(y|β1|4α_↓|4y|β0)/(x|β1|4α_↓|4x|β0)|4α=↓|4y|ur|↔0
1137 |)1|)>|Ly|β1|L|L(y|ur|↔0|)2|)|4α_↓|4y|ur|↔0|)1|))/(x|β2|4α_↓
1138 |4x|β0)|4α=↓|4y|β2>|L|L(y|β2|4α_↓|4y|β1)/(x|β2|4α_↓|4x|β1)|4
1139 α=↓|4y|ur|↔0|)2|)|L|L(y|β3|4α_↓|4y|β2)/(x|β3|4α_↓|4x|β0)|4α=
1139 ↓|4y|β3>|Ly|β2|L|L(y|ur|↔0|)3|)|4α_↓|4y|ur|↔0|)2|))/(x|β3|4α
1140 _↓|4x|β1)|4α=↓|4y|β3>|L|L(y|β3|4α_↓|4y|β2)/(x|β3|4α_↓|4x|β2)
1141 |4α=↓|4y|β3>|Ly|β3>{B7}(44)|?{A12}{A5}|π{H10L12M29}It
1145 is possible to prove that |ε|≤a|β0|4α=↓|4y|β0,
1151 |≤a|β1|4α=↓|4y|ur|↔0|)1|), |≤a|β2|4α=↓|4y|β2,
1153 |πetc., and that the divided di=erences have
1160 important relations to the derivatives of the
1167 function being interpolated; see exercise 15.
1173 Therefore the following calculation {H12}({H10}corresponding
1177 to (44){H12}) {H10}may be used to obtain the
1186 |ε|≤a'|πs:|'{A6}!|4|4|4|4Start with |ε(|≤a|β0,|4|≤a|β1,|4.|4
1189 .|4.|4,|4|≤a|βn)|4|¬L|4(y|β0,|4y|β1,|4.|4.|4.|4,|4y|βn);
1190 |πthen, for |εk|4α=↓|41,|42,|4.|4.|4.|4,|4n>!|4|4|4|4(|πin
1194 this order), set |εy|βj|4|¬L|4(y|βj|4α_↓|4y|βj|βα_↓|β1)/(x|β
1197 j|4α_↓|4x|βj|βα_↓|βk) |πfor |εj|4α=↓|4n, n|4α_↓|41,|4.|4.|4.
1200 |4,|4k>!|4|4|4|4|π(in this order).|'{A6}This
1205 process requires |f1|d32|)(|εn|g2|4α+↓|4n) |πdivisions
1209 and |εn|g2|4α+↓|4n |πsubtractions, so about three-fourths
1215 of the work implied in (41) has been saved.|'
1224 !|4|4|4|4For example, suppose that we want to
1231 estimate |f3|d32|)*3 from the values of 0.*3, 1*3,
1239 2*3, and 3*3, using a cubic polynomial. The divided
1248 di=erences are|'|h|ε|∂x!!|∂y!!|∂y|¬S!!|∂y|¬C!!|∂y|9|1|∂|E|n|
1250 ;|Lx|Ly|Ly|¬S|Ly|¬C|Ly>{A2}{H10L7M29}|L0|L1>|L|L|L0>
1254 |L1|L1|L|L|f1|d32|)>|L|L|L1|L|L|f1|d33|)>|L2|L2|L|L|f3|d32|)
1256 >|L|L|L4>|L3|L6>{A6}{H10L12M29}|πso |εu|g[|g0|g](x)|4α=↓|4u|
1260 g[|g1|g](x)|4α=↓|41, u|g[|g2|g](x)|4α=↓|4|f1|d32|)x(x|4α_↓|4
1261 1)|4α+↓|41, u|g[|g3|g](x)|4α=↓|4|f1|d33|)x(x|4α_↓|41)(x|4α_↓
1262 |42)|4α+↓|4|f1|d32|)x(x|4α_↓|41)|4α+↓|41. |πSetting
1264 |εx|4α=↓|4|f3|d32|) |πgives α_↓|f1|d38|)|4α+↓|43|d38|)|4α+↓|
1266 41|4α=↓|41.25; presumably the ``correct'' value
1271 is |ε|≤)(|f5|d32|))|4α=↓|4|f3|d34|){U20}|≤p|)|4|¬V|41.33.|'
1273 |π!|4|4|4|4It is instructive to note that evaluation
1280 of the interpolation polynomial is just a special
1288 case of the Chinese remainder algorithm of Section
1296 4.3.2, since we know the value of |εu|g[|gn|g](x)
1304 |πmod the relatively prime polynomials |εx|4α_↓|4x|β0,|4.|4.
1309 |4.|4,|4x|4α_↓|4x|βn. |π{H12}({H10}As we have
1313 seen above, |εf|1(x) |πmod |ε(x|4α_↓|4x|β0)|4α=↓|4f|1(x|β0).
1317 {H12}) {H10}Under this interpretation, Newton's
1322 formula (42) |πis precisely the ``mixed radix
1329 representation'' of Eq. 4.3.2<24; and 4.3.2<23
1335 yields another way to compute |ε|≤a|β0,|4.|4.|4.|4,|4|≤a|βn
1341 |πusing the same number of operations as (44).|'
1349 !|4|4|4|4By applying fast Fourier transforms,
1354 it is possible to reduce the running time for
1363 interpolation to |εO{H12}({H10}n(|πlog|4|εn)|g2{H12}){H10},
1366 and a similar reduction can also be made for
1375 related algorithms such as the solution to the
1383 Chinese remainder problem and the evaluation
1389 of an |εn|πth degree polynomial at |εn |πdi=erenthppo*?ee
1397 polynomial at |εn |πdi=erent points; see E. Horowitz,
1405 |εInf. Proc. Letters |≡1 (1972), 157<163, |πR.
1412 Moenck and A. Borodin, |εJ. Comp. Syst. Sci.
1420 |≡8 (1974), 336<385, |πand A. Borodin, |εcomplexity
1427 of Sequential and Parallel Numerical algorithms,
1433 |πed. by J. F. Traub (New York: Academic Press,
1442 1973), 149<180). However, this must be regarded
1449 as a purely theoretical possibility at present,
1456 since the known algorithms have a rather large
1464 overhead factor.|'!|4|4|4|4A remarkable modi_cation
1469 of the method of divided di=erences, whioch applies
1477 to rational functions instead of polynomials,
1483 was introduced by T. N. Thiele in 1909. For a
1493 discussion of Thiele's method of ``reciprocal
1499 di=erences,'' see L. M. Milne-Thompson, |εCalculus
1505 of Finite Di∩erences (|πLondon: MacMillan, 1933),
1511 chapter 5; R. W. Floyd, |εCACM |≡3 (1960), 508.|'
1520 {A12}|≡F|≡o|≡r |≡f|≡u|≡r|≡t|≡h|≡e|≡r |≡r|≡e|≡a|≡d|≡i|≡n|≡g|≡
1522 .|9|4In this section we have barely scratched
1529 the surface of a very large subject in which
1538 many beautiful theories are emerging; a more
1545 comprehensive treatment appears in the book |εComputational
1552 Complexity of Algebraic and Numeric Problems
1558 |πby A. Borodin and I. Munro (New York: American
1567 Elsevier, 1975).|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'
1570 {A12}{H9L11M29}|9|1|≡1|≡.|9|4|ε[|*/OC|\] |πWhat
1572 is a good way to evaluate an ``odd'' polynomial|'
1581 {A6}|εu(x)|4α=↓|4u|β2|βn|βα+↓|β1x|g2|gn|gα+↓|g1|4α+↓|4u|β2|β
1581 n|βα_↓|β1x|g2|gn|gα_↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β1x
1581 ?|;{A3}|9|1|≡2|≡.|9|4[M|*/Pc|\] |πInstead of computing
1586 |εu(x|4α+↓|4x|β0) |πby steps H1, H2 as in the
1594 text, discuss the application of Horner's rule
1601 (2) when |εpolynomial |πmultiplication and addition
1607 are used instead of arithmetic in the domain
1615 of coe∃cients.|'{A3}|9|1|≡3|≡.|9|4|ε[|*/Pc|\]
1618 |πGive a method analogous to Horner's rule, for
1626 evaluating a polynomial in two variables |ε|¬K|βi|βα+↓|βj|β|
1632 ¬E|βn|4u|βi|βjx|giy|gj. |π(This polynomial has
1636 |ε(n|4α+↓|41)(n|4α+↓|42)/2 |πcoe∃cients, and
1639 ``total degree'' |εn.) |πCount the number of
1646 additions and multiplications you use.|'{A3}|9|1|≡4|≡.|9|4|ε
1651 [M|*/Pc|\] |πThe text shows that scheme (3) is
1659 superior to Horner's rule when we are evaluating
1667 a polynomial with real coe∃cients at a complex
1675 point |εz. |πCompare (3) to Horner's rule when
1683 |εboth |πthe coe∃cients and the variable |εz
1690 |πare complex numbers; how many (real) multiplications
1697 and addition-subtractions are required by each
1703 method?|'{A3}|9|1|≡5|≡.|9|4[|εM|*/|↔P|↔c|\] |πCount
1706 the number of multiplications and additions required
1713 by the second-order rule (4).|'|Hβ*?{U0}{H10L12M29}58320#Comp
folio 629 galley 3
1718 iter Programming!(A.-W./Knuth)!ch. 4!f. 629!g.
1722 3D|'{H9L11M29}|9|1|≡6|≡.|9|4[|ε|*/|↔P|↔P|\] |π(L.
1725 de Jong and J. van Leeuwen.) Show how to improve
1735 on steps S1,|4.|4.|4.|4,|4S4 by computing only
1741 about |f1|d32|)|εn |πpowers of |εx.|'{A3}|9|1|≡7|≡.|9|4[M|*/|
1746 ↔P|↔M|\] |πHow can |ε|≤b|β0,|4.|4.|4.|4,|4|≤b|βn
1750 |πbe calculated so that (6) has the value |εu(x|β0|4α+↓|4kh)
1758 |πfor all |εk;|'{A3}|9|1|≡8|≡.|9|4[M|*/|↔P|↔c|\]
1763 |πThe factorial power |εx|gk |πis de_ned to be
1771 |εk*3(|fx|d5k|))|4α=↓|4x(x|4α_↓|41)|4|¬O|4|¬O|4|¬O|4(x|4α_↓|4
1771 k|4α+↓|41). |πExplain how to evaluate |εu|βnx|gn|4α+↓|1|1|¬O
1776 |4|¬O|4|¬O|1|1α+↓|4u|β1x|g1|4α+↓|4u|β0 |πwith
1778 at most |εn |πmultiplications and |ε2n|4α_↓|41
1784 |πadditions, starting with |εx |πand the |εn|4α+↓|43
1791 |πconstants |εu|βn,|4.|4.|4.|4,|4u|β0, 1, n|4α_↓|41.|'
1795 {A3}|9|1|≡9|≡.|9|4[|εM|*/|↔P|↔M|\] |π(H. J. Ryser.)
1799 Show that if |εX|4α=↓|4(x|βi|βj) |πis an |εn|4α⊗↓|4n
1806 |πmatrix, then|'{A6}per(|εX)|4α=↓|4|↔k|4(|→α_↓1)|urnα_↓|≤e|β
1808 1α_↓|4|¬O|4|¬O|4|¬O|4α_↓|≤e|βn|)|)|≥u|uc|)1|¬Ei|¬En|)|4|↔k|u
1808 c|)1|¬Ej|¬En|)|4|≤e|βjx|βi|βj|;{A6}|πsummed over
1811 all |ε2|gn |πchoices of |ε|≤e|β1,|4.|4.|4.|4,|4|≤e|βn
1816 |πequal to 0 or 1 independently. count the number
1825 of addition and multiplication operations required
1831 to evaluate per |ε(X) |πby this formula.|'{A3}|≡1|≡0|≡.|9|4[
1838 |εM|*/|↔P|↔O|\] |πThe permanent of an |εn|4α⊗↓|4n
1844 |πmatrix |εX|4α=↓|4(x|βi|βj) |πmay be calculated
1849 as follows: Start with the |εn |πquantities |εx|β1|β1,
1857 x|β1|β2,|4.|4.|4.|4,|4x|β1|βn. |πFor |ε1|4|¬E|4k|4|¬W|4n,
1860 |πassume that the (|ε|fn|d5k|)) |πquantities
1865 |εA|βk|βS |πhave been computed, for all |εk-|πelement
1872 subsets |εS |πof |ε|¬T1,|42,|4.|4.|4.|4,|4n|¬Y,
1876 |πwhere |εA|βk|βS|4α=↓|4|¬K|4x|β1|βj|m1|4.|4.|4.|4x|βk|βj|mk
1877 |πsummed over all |εk*3 |πpermutations |εj|β1|4.|4.|4.|4j|βk
1883 |πof the elements of |εS; |πthen form all of
1893 the sums|'{A6}|εA|β(|βk|βα+↓|β1|β)|βS|4α=↓|4|↔k|uc|)j|¬AS|)|
1895 4A|βk|β(|βS|βα_↓|β|¬T|βj|β|¬Y|β)x|β(|βk|βα+↓|β1|β)|βj.|;
1896 {A6}|πWe have per(|εX)|4α=↓|4A|βn|β|¬T|β1|β,|4|β.|4|β.|4|β.|
1898 4|β,|4|βn|β|¬Y.|'|π!!|1|1How many additions and
1903 multiplications does this method require? How
1909 much temporary storage is needed?|'{A3}|≡1|≡1|≡.|9|4[|εM|*/|↔
1914 C|↔c|\] |πIs there any way to evaluate the permanent
1923 of a general |εn|4α⊗↓|4n |πmatrix using a number
1931 of operations which does not grow exponentially
1938 with |εn?|'{A3}|≡1|≡2|≡.|9|4[M|*/|↔C|↔c|\] |πWhat
1942 is the minimum number of multiplications required
1949 to multiply two |εn|4α⊗↓|4n |πmatrices? Can the
1956 total number of operations be reduced to less
1964 than |εO(n|π|gl|gg|4|g7)?|'{A3}|≡1|≡3|≡.|9|4[|εM|*/|↔P|↔L|\]
1967 |πFind the inverse of the general _nite Fourier
1975 transform (37), by expressing |εF(t|β1,|4.|4.|4.|4,|4t|βn)
1980 |πin terms of the values of |εf|1(s|β1,|4.|4.|4.|4,|4s|βn).
1987 [Hint|*/:|\ |πSee Eq. 1.2.9<13.]|'{A3}|≡1|≡4|≡.|9|4[|εHM|*/|↔P
1991 |↔l|\] |π(a) (|ε``Fast Fourier transforms.'')
1996 |πShow that the scheme (40) can be used to evaluate
2006 the one-dimensional fourier transform|'{A6}|εf|1(s)|4α=↓|4|↔
2010 k|uc|)0|¬Et|¬W2|gn|)|4F(t)|≤v|gs|gt,!!|≤v|4α=↓|4e|ur2|≤pi/2|
2010 gn|)|),!!0|4|¬E|4s|4|¬W|42|gn,|;{A6}|πusing arithmetic
2013 on complex numbers. (b) Apply this result to
2021 prove that we can obtain the coe∃cients of the
2030 product of two given polynomials, |εu(z)v(z),
2036 |πin |εO(n|4|πlog|4|εn) |πoperations of (exact)
2041 addition and multiplication of complex numbers,
2047 if |εu(z) |πand |εv(z) |πare |εn|πth degree polynomials
2055 with complex coe∃cients. [|εHint|*/: |\|πconsider
2060 the product of fourier transforms of the coe∃cients.]|'
2068 {A3}|≡1|≡5|≡.|9|4[|εHM|*/|↔P|↔l|\] |πThe |εn|πth
2071 |εdivided di∩erence f|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn)
2074 |πof a function |εf|1(x) |πat |εn|4α+↓|41 |πdistinct
2081 points |εx|β0,|4x|β1,|4.|4.|4.|4,|4x|βn |πis
2084 de_ned by the formula |εf|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn)|
2088 4α=↓|4{H12}({H9}f|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn|βα_↓|β1)|
2088 4α_↓|4f|1(x|β1,|4.|4.|4.|4,|4x|βn|βα_↓|β1,|4x|βn){H12}){H9}/
2088 (x|β0|4α_↓|4x|βn), |πfor |εn|4|¬Q|40. |πThus
2092 |εf|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|4|¬K|β0|β|¬E|βk|β
2092 |¬E|βn|4f|1(x|βk)/|≤p|ur|)0|¬Ej|¬En,j|=|↔6α=↓k|)(x|βk|4α_↓|4
2092 x|βj) |πis a symmetric function of its |εn|4α+↓|41
2100 |πarguments. (a) Prove that |εf|1(x|β0,|4.|4.|4.|4,|4x|βn)|4
2104 α=↓|4f|g(|gn|g)(|≤u)/n*3, |πfor some |ε|≤u |πbetween
2109 min(|εx|β0,|4.|4.|4.|4,|4x|βn) |πand max(x|β0,|4.|4.|4.|4,|4
2111 x|βn), |πif the |εn|πth derivative |εf|1|g(|gn|g)(x)
2117 |πexists and is continuous. [|εHint|*/: |\|πProve
2123 that|'{A6}|εf|1(x|β0,|4x|β1,|4.|4.|4.|4,|4x|βn)|4α=↓|4|↔j|ur
2124 1|)0|)dt|β1|↔j|urt|β1|)0|)dt|β2|4|¬O|4|¬O|4|¬O|4|↔j|urt|βn|β
2124 α_↓|β1|)0|)dt|βnf|g(|gn|g){H12}({H10}x|β0(1|4α_↓|4t|β1)|4α+↓
2124 |4x|β1(t|β1|4α_↓|4t|β2)|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4x|βn|β
2124 α_↓|β1(t|βn|βα_↓|β1|4α_↓|4t|βn)|4α+↓|4x|βn(t|βn|4α_↓|40){H12
2124 }){H10}.|;{A6}|π(This formula also de_nes |εf|1(x|β0,|4x|β1,
2129 |4.|4.|4.|4,|4x|βn) |πin a useful manner when
2135 the |εx|βj |πare not distinct.)] If |εy|βj|4α=↓|4f|1(x|βj),
2142 |πshow that |ε|≤a|βj|4α=↓|4f|1(x|β0,|4.|4.|4.|4,|4x|βj)
2145 |πin Newton's interpolation polynomial (42).|'
2150 {A3}|≡1|≡6|≡.|9|4[|εM|*/|↔P|↔P|\] |πHow can we
2154 readily compute the coe∃cients of |εu|g[|gn|g](x)|4α=↓|4u|βn
2159 x|gn|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β0, |πif
2161 we are given the values of |εx|β0, x|β1,|4.|4.|4.|4,|4x|βn|β
2168 α_↓|β1, |≤a|β0, |≤a|β1,|4.|4.|4.|4,|4|≤a|βn |πin
2172 Newton's interpolation polynomial (15)?|'{A3}|≡1|≡7|≡.|9|4[|
2176 εM|*/|↔M|↔o|\] |πIs there a way to evaluate the
2184 polynomial|'{A6}|ε|↔k|uc|)1|¬Ei|¬Wj|¬En|)|4x|βix|βj|4α=↓|4x|
2185 β1x|β2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4x|βn|βα_↓|β1x|βn|;
2186 {A6}|πwith fewer than |εn|4α_↓|41 |πmultiplications
2191 and |ε2n|4α_↓|44 |πadditions? (There are (|ε|fn|d52|))
2197 |πterms.)|'{A3}|≡1|≡8|≡.|9|4[|εM|*/|↔P|↔c|\] |πIf
2200 the fourth-degree scheme (9) were changed to|'
2207 {A6}|εy|4α=↓|4(x|4α+↓|4|≤a|β0)x|4α+↓|4|≤a|β1,!!u(x)|4α=↓|4{H
2207 12}({H9}(y|4α_↓|4x|4α+↓|4|≤a|β2)y|4α+↓|4|≤a|β3{H12}){H9}|≤a|
2207 β4,|;{A6}|πwhat formulas for computing the |ε|≤a|βj'|πs
2214 in terms of the |εu|βk'|πs would take the place
2223 of (10)?|'{A3}|≡1|≡9|≡.|9|4[|εM|*/|↔P|↔M|\] |πExplain
2227 how to determine the adapted coe∃cients |ε|≤a|β0,
2234 |≤a|β1,|4.|4.|4.|4,|4|≤a|β5 |πin (11) from the
2239 coe∃cients |εu|β5,|4.|4.|4.|4,|4u|β1, u|β0 |πof
2243 |εu(x) |πand _nd the |ε|≤a'|πs for the particular
2251 polynomial |εu(x)|4α=↓|4x|g5|4α+↓|45x|g4|4α_↓|410x|g3|4α_↓|4
2252 50x|g2|4α+↓|413x|4α+↓|460.|'{A3}|≡2|≡0|≡.|9|4[|*/|↔P|↔O|\]
2254 |πWrite a |¬m|¬i|¬x program which evaluates a
2261 _fth-degree polynomial according to scheme (11);
2267 try to make the program as e∃cient as possible,
2276 by making slight modi_cations to (11). Use |¬m|¬i|¬x's
2284 ⊗oating-point arithmetic operators.|'{A3}|≡2|≡1|≡.|9|4[|*/|↔P
2287 |↔c|\] |πFind two more ways to evaluate the polynomial
2296 |εx|g6|4α+↓|413x|g5|4α+↓|449x|g4|4α+↓|433x|g3|4α_↓|461x|g2|4
2296 α_↓|437x|4α+↓|43 |πby scheme (12), using the
2302 two roots of (15) which were not considered in
2311 the text.|'{A3}|≡2|≡2|≡.|9|4[|ε|*/|↔O|↔l|\] |πWhat
2315 is the scheme for evaluating |εx|g6|4α_↓|43x|g5|4α+↓|4x|g4|4
2320 α_↓|42x|g3|4α+↓|4x|g2|4α_↓|43x|4α_↓|41, |πusing
2322 Pan's method (16)?|'{A6}|≡2|≡3|≡.|9|4[|εHM|*/|↔L|↔c|\]
2326 |π(J. Eve.) Let |εf|1(z)|4α=↓|4a|βnz|gn|4α+↓|4a|βn|βα_↓|β1z|
2329 gn|gα_↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|β0
2330 |πbe a polynomial of degree |εn |πwith real coe∃cients,
2339 having at least |εn|4α_↓|41 |πroots with a nonnegative
2347 real part. Let|'{A6}|h|εh(z)|4|∂α=↓|4a|βn|βα_↓|β1z|gn|gα_↓|g
2350 1|4α+↓|4a|βn|βα_↓|β3z|gn|gα_↓|g2|4α+↓|1|1.|4.|4.|1|1α+↓|4a|β
2350 (|βn|βα_↓|β1|β)|4|π|βm|βo|βd|4|β2|εz|gn|gα_↓|g1|g(|g)|g|πm|g
2350 o|gd|4|g2.|4|E|n|;|ε| g(z)|4|Lα=↓|4a|βnz|gn|4α+↓|4a|βn|βα_↓|
2351 β2z|gn|gα_↓|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4a|βn|4|π|βm|βo|
2351 βd|4|β2|εz|gn|4|π|gm|go|gd|4|g2,>{A4}|ε| h(z)|4|Lα=↓|4a|βn|β
2352 α_↓|β1z|gn|gα_↓|g1|4α+↓|4a|βn|βα_↓|β3z|gn|gα_↓|g3|4α+↓|1|1|¬
2352 O|4|¬O|4|¬O|1|1α+↓|4a|β(|βn|βα_↓|β1|β)|4|π|βm|βo|βd|4|β2|εz|
2352 g(|gn|gα_↓|g1|g)|4|π|gm|go|gd|4|g2.>{A6}Assume
2354 that |εh(z) |πis not identically zero.|'|Hβ{U0}{H10L12M29}58
folio 632 galley 4
2360 320#Computer Programming!(A.-W./Knuth)!ch. 4!f.
2363 632!g. 4D|'{A12}{H9L11M29}!!|1|1a)|9|1Show that
2367 |εg(z) |πhas at least |εn|4α_↓|42 |πimaginary
2373 roots (i.e., roots whose real part is zero),
2381 and |εh(z) |πhas at least |εn|4α_↓|43 |πimaginary
2388 roots. [|εHint|*/: |\|πConsider the number of
2394 times the path |εf|1(z) |πcircles the origin
2401 as |εz |πgoes around the path shown in fig. 15,
2411 for a su∃ciently large radius |εR.]|'|π!!|1|1b)|9Prove
2418 that the squares of the roots of |εg(z)|4α=↓|40,
2426 h(z)|4α=↓|40 |πare all rea.|'{A3}|≡2|≡4|≡.|9|4[|εM|*/|≤P|≤M|\
2430 ] |πFind values of |εc |πand |ε|≤a|βk, |≤b|βk
2438 |πsatisfying the conditions of Theorem|εu(x)|4α=↓|4(x|4α+↓|4
2442 7)(x|g2|4α+↓|46x|4α+↓|410)(x|g2|4α+↓|44x|4α+↓|45)(x|4α+↓|41)
2442 . |πChoose these values so that |ε|≤b|β2|4α=↓|40.
2449 |πGive two di=erent solutions to this problem*3|'
2456 {A3}|≡2|≡5|≡.|9|4[|εM|*/|↔P|↔c|\] |πWhen the construction
2460 in the proof of Theorem M is applied to the (ine∃cient)
2471 polynomial chain|'{A6}|ε|≤l|β1|4|∂α=↓|4|≤a|β1|4α+↓|4|≤l|β0,!
2473 !|≤l|β2|4|∂α=↓|4|→α_↓|≤l|β0|4α_↓|4|≤l|β0,!!|≤l|β3|4|∂α=↓|4|≤
2473 l|β1|4α+↓|4|≤l|β1,!!|≤l|β4|4|∂α=↓|4|≤a|β2|4α⊗↓|4|≤l|β3,|;
2474 {A3}| |≤l|β5|4|Lα=↓|4|≤l|β0|4α_↓|4|≤l|β0,| |≤l|β6|4|Lα=↓|4|≤
2474 a|β6|4α_↓|4|≤l|β5,| |≤l|β7|4|Lα=↓|4|≤a|β7|4α+↓|4|≤l|β6,| |≤l
2474 |β8|4|Lα=↓|4|≤l|≤l|β7|4α⊗↓|4|≤l|β7,>{A3}|πhow
2476 can |ε|≤b|β1, |≤b|β2,|4.|4.|4.|4,|4|≤b|β9 |πbe
2480 expressed in terms of |ε|≤a|β1,|4.|4.|4.|4,|4|≤a|β8?|'
2485 {A3}|≡2|≡6|≡.|9|4[M|*/|↔P|↔O|\] |π(a) Give the
2489 polynomial chain corresponding to Horner's rule
2495 for evaluating polynomials of degree |εn|4α=↓|43.
2501 |π(b) Using the construction in the proof of
2509 Theorem A, express |ε|≤k|β1, |≤k|β2, |≤k|β3,
2515 |πand the result polynomial |εu(x) |πin terms
2522 of |ε|≤b|β1, |≤b|β2, |≤b|β3, |≤b|β4, |πand |εx.
2529 |π(c) Show that the result set obtained in (b),
2538 as |ε|≤b|β1, |≤b|β2, |≤b|β3, |≤b|β4 |πindependently
2544 assume all real values, omits certain vectors
2551 in the result set of (a).|'{A3}|≡2|≡7|≡.|9|4|ε[M|*/|↔P|↔P|\]
2558 |πLet |εR |πbe a set which includes all |ε(n|4α+↓|41)-|πtupl
2566 es |ε(q|βn,|4.|4.|4.|4,|4q|β1,|4q|β0) |πof real
2570 numbers such that |εq|βn|4|=|↔6α=↓|40; |πprove
2575 that |εR |πdoes not have at most |εn |πdegrees
2584 of freedom.|'{A3}|≡2|≡8|≡.|9|4[|εHM|*/|↔P|↔c|\]
2587 |πShow that if |εf|β0(|≤a|β1,|4.|4.|4.|4,|4|≤a|βs),|4.|4.|4.
2590 |4,|4f|βs(|≤a|β1,|4.|4.|4.|4,|4|≤a|βs) |πare
2592 multivariate polynomials with integer coe∃cients,
2597 then there is a nonzero polynomial |εg(x|β0,|4.|4.|4.|4,|4x|
2603 βs) |πwith integer coe∃cients wuch that |εg{H12}({H9}f|β0(|≤
2609 a|β1,|4.|4.|4.|4,|4|≤a|βs),|4.|4.|4.|4,|4|≤a|βs),|4.|4.|4.|4
2609 ,|4f|βs(|≤a|β1,|4.|4.|4.|4,|4|≤a|βs){H12}){H9}|4α=↓|40
2610 |πfor all real |ε|≤a|β1,|4.|4.|4.|4,|4|≤a|βs.
2614 (|πHence any polynomials chain with |εs |πparameters
2621 has at most |εs |πdegrees of freedom.) [|εHint|*/:
2629 |\|πUse the theorems about ``algebraic dependence''
2635 which are found, for example, in B. L. van der
2645 Waerden's |εModern Algebra, |πtr. by Fred Blum
2652 (New York: Ungar, 1949), Section 64.]|'{A3}|≡2|≡9|≡.|9|4[|εM
2658 |*/|↔P|↔c] |\|πLet |εR|β1, R|β2,|4.|4.|4.|4,|4R|βm
2662 |πall be sets of |ε(n|4α+↓|41)-|πtuples of real
2669 numbers having at most |εt |πdegrees of freedom.
2677 Show that the union |εR|β1|4|↔q|4R|β2|4|↔q|4|¬O|4|¬O|4|¬O|4|
2681 ↔q|4R|βm |πalso has at most |εt |πdegrees of
2689 freedom.|'{H9L11M29}{A3}|≡3|≡0|≡.|9|4[|εM|*/|↔P|↔l|\]
2691 |πProve that a polynomial chain with |εm|β1 |πchain
2699 multiplications and |εm|β2 |πparameter multiplications
2704 has at most |ε2m|β1|4α+↓|4m|β2|4α+↓|4|≤d|β0|βm|m1
2708 |πdegrees of freedom. [|εHint|*/: |\|πGeneralize
2713 Theorem M, showing that the _rst chain multiplication
2721 and each parameter multiplication can essentially
2727 introduce only one new parameter into the result
2735 set.]|'{A3}|≡3|≡1|≡.|9|4[|εM|*/|↔P|↔L|\] |πProve
2738 that a polynomial chain capable of computing
2745 all |εmonic |πpolynomials of degree |εn |πhas
2752 at least |"l|εn/2|"L |πmultiplications and at
2758 least |εn |πaddition-subtractions.|'{A3}|≡3|≡2|≡.|9|4[|εM|*/|
2761 ↔P|↔M|\] |πFind a polynomial chain of minimum
2768 possible length which can compute all polynomials
2775 of the form |εu|β4x|g4|4α+↓|4u|β2x|g2|4α+↓|4u|β0;
2779 |πprove that its length is minimal.|'{A3}|π|≡3|≡3|≡.|9|4[|εM
2785 |*/|↔P|↔C|\] |πLet |εn|4|¬R|43 |πbe odd. Prove
2791 that a polynomial chain with |ε|"ln/2|"L|4α+↓|41
2797 |πmultiplication steps cannot compute all polynomials
2803 of degree |εn |πunless it has at least |εn|4α+↓|42
2812 |πaddition-subtraction steps. |ε[Hint|*/: |\|πSee
2816 exercise 30.]|'{A3}|≡3|≡4|≡.|9|4[|εM|*/|↔P|↔o|\]
2819 |πLet |ε|≤l|β0,|4|≤l|β1,|4.|4.|4.|4,|4|≤l|βr
2821 |πbe a polynomial chain in which all addition
2829 and subtraction steps are parameter steps, and
2836 which contains at least one parameter multiplication.
2843 Assume that this scheme has |εm |πmultiplications
2850 and |εk|4α=↓|4r|4α_↓|4m |πaddition-subtractions,
2853 and that the polynomial computed by the chain
2861 has maximum degree |εn. |πProve that all polynomials
2869 computable by this chain, for which the coe∃cient
2877 of |εx|gn |πis not zero, can be computed by another
2887 chain which has at most |εm |πmultiplications
2894 and at most |εk |πadditions, and no subtractions;
2902 and whose last step is the only paramter multiplication.|'
2911 {A3}|≡3|≡5|≡.|9|4[|εM|*/|↔P|↔C|\] |πShow that
2914 any polynomial chain which computes a general
2921 fourth degree polynomial using only three multiplications
2928 must have at least _ve addition-subtractions.
2934 |ε[Hint|*/: |\|πAssume that there are only four
2941 addition-subtractions, and show that exercise
2946 34 applies; this means the scheme must have a
2955 particular form which is incapable of representing
2962 all fourth degree polynomials.]|'{A3}|≡3|≡6|≡.|9|4[|εM|*/|↔P|
2966 ↔p|\] |πShow that any polynomial chain which
2973 computes a general sixth-degree polynomial using
2979 only four multiplications must have at least
2986 seven addition-subtractions. (Cf. exercise 35.)|'
2991 {A3}|≡3|≡7|≡.|9|4[|εM|*/|↔P|↔O|\] |π(T. S. Motzkin.)
2995 Show that ``almost all'' rational functions of
3002 the form|'{A6}|ε(u|βnx|gn|4α+↓|4u|βn|βα_↓|β1x|gn|gα_↓|g1|4α+
3004 ↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β1x|4α+↓|4u|β0)/(x|gn|4α+↓|4v|β
3004 n|βα_↓|β1x|gn|gα_↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4v|β1x|4α
3004 +↓|4v|β0),|;{A4}|πwith coe∃cients in a _eld |εS,
3011 |πcan be evaluated using the scheme|'{A6}|ε|≤a|β1|4α+↓|4|≤b|
3017 β1/{H12}({H9}x|4α+↓|4|≤a|β2|4α+↓|4|≤b|β2/(x|4α+↓|1|1.|4.|4.|
3017 4|≤b|βn/(x|4α+↓|4|≤a|βn|βα+↓|β1)|4|¬O|4|¬O|4|¬O){H12}){H9},|
3017 ;{A6}|(fpr siotab_e |ε|≤a|βj, |≤b|βj |πin |εS.
3024 (|πThis continued fraction scheme has |εn |εdivisions
3031 and |ε2n |πadditions; by ``almost all'' rational
3038 functions we mean all except those whose coe∃cients
3046 satisfy some nontrivial polynomial equation.)
3051 Determine the |ε|≤a'|πs and |ε|≤b'|πs for the
3058 rational function |ε(x|g2|4α+↓|410x|4α+↓|429)/(x|g2|4α+↓|48x
3060 |4α+↓|419).|'{A3}|≡3|≡8|≡.|9|4[HM|*/|↔L|↔P|\]
3062 |π(A. M. Garsia, 1962.) The purpose of this exercise
3071 is to prove that Horner's rule is really optimal
3080 if no preliminary adaptation of coe∃cients is
3087 made; we need |εn |πmultiplications and |εn |πadditions
3095 to compute |εu|βnx|gn|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4u|β1x|4α
3097 +↓|4u|β0, |πif the variables |εu|βn,|4.|4.|4.|4,|4u|β1,
3102 u|β0, x, |πand arbitrary constants are given.
3109 consider chains which are as before except that
3117 |εu|βn,|4.|4.|4.|4,|4u|β1, u|β0, x |πare each
3122 considered to be variables; we may say, for example,
3131 that |ε|≤l|βα_↓|βj|βα_↓|β1|4α=↓|4u|βj, |≤l|β0|4α=↓|4x.
3134 |πIn order to show that Horner's rule is best,
3143 it is convenient to prove a somewhat more general
3152 theorem: Let |εA|4α=↓|4|ε(a|βi|βj), 0|4|¬E|4i|4|¬E|4m,
3156 0|4|¬E|4j|4|¬E|4n, |πbe an |ε(m|4α+↓|41)|4α⊗↓|4(n|4α+↓|41)
3160 |πmatrix of real numbers, of rank |εn|4α+↓|41;
3167 |πand let |εB|4α=↓|4(b|β0,|4.|4.|4.|4,|4b|βm)
3170 |πbe a vector of real numbers. Prove that |εany
3179 polynomial chain which computes|'{A6}P(x;|4u|β0,|4.|4.|4.|4,
3183 |4u|βn)|4α=↓|4|↔k|uc|)0|¬Ei|¬Em|)(a|βi|β0u|β0|4α+↓|1|1|¬O|4|
3183 ¬O|4|¬O|1|1α+↓|4a|βi|βnu|βn|4α+↓|4b|βi)x|gi|;
3184 {A6}involves at least n chain multiplications.
3190 |π(Note that this does not mean only that we
3199 are considering some _xed chain in which the
3207 parameters |ε|≤a|βj |πare assigned values depending
3213 on |εA |πand |εB; |πit means that both the chain
3223 |εand |πthe values of the |ε|≤a'|πs may depend
3231 on the given matrix |εA |πand vector |εB. |πNo
3240 matter how |εA, B, |πand the values of |ε|≤a|βj
3249 |πare chosen, it is impossible to compute |εP(x;|4u|β0,|4.|4
3256 .|4.|4,|4u|βn) |πwithout doing |εn ``|πchainstep''
3261 multiplications.) The assumption that |εA |πhas
3267 rank |εn|4α+↓|41 |πimplies that |εm|4|¬R|4n.
3272 [Hint|*/: |\|πShow that from any such scheme we
3280 can derive another which has one less chain multiplication
3289 and which has |εn |πdecreased by one.]|'β*?*?{U0}{H10L12M29}58
folio 635 galley 5
3296 320#Computer Programming!(A.-W./knuth)!ch. 4!f.
3299 g. 5D|'{A12}{H9L11M29}|≡3|≡9|≡.|9|4[M|*/|↔P|↔m|\]
3302 |π(T. S. Motzkin, 1954.) Show that schemes of
3310 the form |εw|β1|4α=↓|4x(x|4α+↓|4|≤a|β1)|4α+↓|4|≤b|β1,
3313 w|βk|4α=↓|4w|βk|βα_↓|β1(w|β1|4α+↓|4|≤g|βkx|4α+↓|4|≤a|βk)|4α+
3313 ↓|4|≤d|βkx|4α+↓|4|≤b|βk |πfor |ε1|4|¬W|4k|4|¬E|4m,
3316 |πwhere the |ε|≤a|βk, |≤b|βk |πare real and the
3324 |ε|≤g|βk|≤d|βk |πare integers, can be used to
3331 evaluate all monic polynomials of degree 2|εm
3338 |πover the real numbers. (We may have to choose
3347 the |ε|≤g|βk |πand |ε|≤d|βk |πdi=erently for
3353 di=erent polynomials.) Try to let |ε|≤d|βk|4α=↓|40
3359 |πwhenever possible.|'*?*?*?*?{H9L11M29}{A3}|≡4|≡0|≡.|9|4[|εM|*/|
3361 ↔M|↔O|\] |πCan the lower bound in the number
3369 of multiplications in Theorem C be raised from
3377 |ε|"ln/2|"L|4α+↓|41 |πto |ε|"pn/2|"P|4α+↓|41?
3380 |π(Cf. exercise 33. An unfounded remark that
3387 Belaga [|εDokladi Akad. Nauk SSSR |≡1|≡2|≡3 (1958),
3394 775<777] |πgave such an improvement has appeared
3401 several times in the literature.)|'{A3}|≡4|≡1|≡.|9|4[|ε|*/|↔P
3406 |↔P|\] |π(Oscar Buneman.) Show that the real
3413 and imaginary parts of |ε(a|4α+↓|4bi)(c|4α+↓|4di)
3418 |πcan be obtained by doing 3 multiplications
3425 and 5 additions of real numbers.|'|≡4|≡2|≡.|9|4[|ε|*/|↔L|↔o|\
3431 ] |π(M. Paterson and L. Stockmeyer.) (a) Prove
3439 that a polynomial chain with |εm|4α=↓|42 |πchain
3446 multiplications has at most |εm|g2|4α+↓|41 |πdegrees
3452 of freedom. (b) Show that for all |εn|4|¬R|42
3460 |πthere exist polynomials of degree |εn, |πall
3467 of whose coe∃cients are 0 or 1, which cannot
3476 be evaluated by any polynomial chain with lesss
3484 than |"l{U19}|εn|)|"L |πmultiplications, if we
3489 require all parameters |ε|≤a|βj |πto be integers.
3496 (c) Show that any polynomial of degree |εn |πwith
3505 integer coe∃cients can be evaluated by an all-integer
3513 algorithm which performs at most |ε2|"l{U19}n|)|"L
3519 |πmultiplications, if we don't care how many
3526 additions we do.|'{A3}|≡4|≡3|≡.|9|4[|*/|ε|↔P|↔P|\]
3530 |πExplain how to evaluate |εx|gn|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+
3534 ↓|4x|4α+↓|41 |πwith |ε2l(n|4α+↓|41)|4α_↓|42 |πmultiplication
3537 s and |εl(n|4α+↓|41) |πadditions (no divisions
3543 or subtractions).|'{H10L12M29}{A24}|≤⊂|∨4|∨.|∨7|∨.|9|4|∨M|∨A
3545 |∨N|∨I|∨P|∨U|∨L|∨A|∨T|∨I|∨O|∨N|9|1|∨O|∨F|9|1|∨P|∨O|∨W|∨E|∨R|
3545 9|1|∨S|∨E|∨R|∨I|∨E|∨S|'{A12}If we are given two
3551 power series|'{A6}|εU(z)|4α=↓|4U|β0|4α+↓|4U|β1z|4α+↓|4U|β2z|
3553 g2|4α+↓|1|1|¬O|4|¬O|4|¬O|4,!!V(z)|4α=↓|4V|β0|4α+↓|4V|β1z|4α+
3553 ↓|4V|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|4,|J!(1)|;{A6}|πwhose
3555 coe∃cients belong to a _eld, we can form their
3564 sum, thier product, their quotient, etc., to
3571 obtain new power series. A polynomial is obviously
3579 a special case of a power series, in which there
3589 are only _nitely many terms.|'!|4|4|4|4Of course,
3596 only a _nite number of terms can be represennted
3605 and stored within a computer, so it makes sense
3614 to ask whether power series arithmetic is even
3622 possible on computers; and if it is possible,
3630 what makes it di=erent from polynomial arithmetic?
3637 The answer is that we work only with the _rst
3647 |εN |πcoe∃cients of the powerseries, where |εN
3654 |πis a parameter which may in principle be arbitrarily
3663 large; instead of ordinary polynomial arithmetic,
3669 we are essentially doing polynomial arithmetic
3675 modulo |εz|gN, |πand this often leads to a seomewhat
3684 di=erent point of view. Furthermore, special
3690 operations, like ``reversion,'' can be performed
3696 on power series but not on polynomials, since
3704 polynomials are not closed under these operations.|'
3711 !|4|4|4|4Manipulation of power series has several
3717 applications to numerical analysis, but perhaps
3723 its greatest use is the determination of asymptotic
3731 expansions (as we have seen in Section 1.2.11.3),
3739 or the calculation of quantities de_ned by certain
3747 generating functions. The latter applications
3752 make it desirable to calculate the coe∃cients
3759 exactly, instead of with ⊗oating-point arithmetic.
3765 All of the algorithms in this section, with obvious
3774 exceptions, can be done using rational operations
3781 only, so the techniques of Section 4.5.1 can
3789 be used to obtain exact results when desired.|'
3797 !|4|4|4|4The calculation of |εW(z)|4α=↓|4U(z)|4|¬N|4V(z)
3801 |πis, of course, trivial, since we have |εW|βn|4α=↓|4U|βn|4|
3808 ¬N|4V|βn |πfor |εn|4α=↓|40, 1, 2,|4.|4.|4. |πIt
3814 is also easy to calculate |εW(z)|4α=↓|4U(z)V(z),
3820 |πusing the familiar ``Cauchy product rule'':|'
3826 {A6}|εW|βn|4α=↓|4|↔k|uc|)0|¬Ek|¬En|)|4U|βkV|βn|βα_↓|βk|4α=↓|
3826 4U|β0V|βn|4α+↓|4U|β1V|βn|βα_↓|β1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+
3826 ↓|4U|βnV|β0.|J!(2)|;{A6}|π!|4|4|4|4The quotient
3829 |εW(z)|4α=↓|4U(z)/V(z), |πwhen |εV|β0|4|=|↔6α=↓|40,
3832 |πcan be obtained by interchanging |εU |πand
3839 |εW |πin (2); we obtain the rule|'{A6}|h|εW|βn|4|∂α=↓|4(U|βn
3846 |4α_↓|4W|β0V|βn|4α_↓|4W|β1V|βn|βα_↓|β1|4α_↓|1|1|¬O|4|¬O|4|¬O
3846 |1|1α_↓|4W|βn|βα_↓|β1V|β1)/V|β0.|E|n|;| W|βn|4|Lα=↓|4|↔aU|βn
3847 |4α_↓|4|↔k|uc|)0|¬Ek|¬Wn|)|4W|βkV|βn|βα_↓|βk|↔s|↔hV|β0>
3848 {A4}|Lα=↓|4(U|βn|4α_↓|4W|β0V|βn|4α_↓|4W|β1V|βn|βα_↓|β1|4α_↓|
3848 1|1|¬O|4|¬O|4|¬O|1|1α_↓|4W|βn|βα_↓|β1V|β1)/V|β0.|J!(3)>
3849 {A6}|πThis recurrence relation for the |εW'|πs
3855 makes it easy to determine |εW|β0, W|β1, W|β2,|4.|4.|4.
3863 |πsuccessively, without inputting |εU|βn |πand
3868 |εV|βn |πuntil after |εW|βn|βα_↓|β1 |πhas been
3874 computed. Let us say that a power-series manipulation
3882 algorithm with the latter property is ``on-line'';
3889 an on-line algorithm can be used to determine
3897 |εN |πcoe∃cients |εW|β0, W|β1,|4.|4.|4.|4,|4W|βN|βα_↓|β1
3901 |πof the result without knowing |εN |πin advance,
3909 so it is possible in theory to run the algorithm
3919 inde_nitely and compute the entire power series;
3926 or to run it until a certain condition is met.
3936 (The opposite of ``on-line'' is ``o=-line.'')|'
3942 !|4|4|4|4If the coe∃cients |εU|βk |πand |εV|βk
3948 |πare integers but the |εW|βk |πare not, recurrence
3956 (3) involves computation with fractions. This
3962 can be avoided by the all-integer approach described
3970 in exercise 2.|'!|4|4|4|4Let us now consider
3977 the operation of computing |εW(z)|4α=↓|4V(z)|g|≤a,
3982 |πwhere |ε|≤a |πis an ``arbitrary'' power. For
3989 example, we could calculate the square root of
3997 |εV(z) |πby taking |ε|≤a|4α=↓|4|f1|d32|), |πor
4002 we could _nd |εV(z)|gα_↓|g1|g0 |πor even |εV(z)|g|≤p.
4009 |πIf |εV|βm |πis the _rst nonzero coe∃cient of
4017 |εV(z), |πwe have|'{A6}{A7}(4)|E|?{B7}|εV(z)|4|∂α=↓|4V|βmz|g
4021 m{H12}({H10}1|4α+↓|4(V|βm|βα+↓|β1/V|βm)z|4α+↓|4(V|βm|βα+↓|β2
4021 /V|βm)z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O{H12}){H10},|;
4022 {A4}| V(z)|g|≤a|4|Lα=↓|4V|ur|≤a|)m|)z|g|≤a|gm{H12}({H10}1|4α
4022 +↓|4(V|βm|βα+↓|β1/V|βm)z|4α+↓|4(V|βm|βα+↓|β2/V|βm)z|g2|4α+↓|
4022 1|1|¬O|4|¬O|4|¬O{H12}){H10}|g|≤a.>{A6}|πThis
4024 will be a power series if and only if |ε|≤am
4034 |πis a nonnegative integer. From (4) we can see
4043 that the problem of computing general powers
4050 can be reduced to the case that |εV|β0|4α=↓|41;
4058 |πthen the problem is to _nd coe∃cients of|'{A6}|εW(z)|4α=↓|
4066 4(1|4α+↓|4V|β1z|4α+↓|4V|β2z|g2|4α+↓|4V|β3z|g3|4α+↓|1|1|¬O|4|
4066 ¬O|4|¬O)|g|≤a.|J!(5)|;{A6}|πClearly |εW|β0|4α=↓|41|g|≤a|4α=↓
4068 |41.|'|π!|4|4|4|4The obvious way to _nd the coe∃cients
4076 of (5) is to use the binomial theorem (Eq. 1.2.9<19),
4086 or (if |ε|≤a |πis a positive integer) to try
4095 repeated squaring as in Section 4.6.3, but a
4103 much simpler and more e∃cient device for calculating
4111 powers has been suggested by J. C. P. Miller.
4120 [See P. Henrici, |εJACM |≡3 (1956), 10<15.] |πIf
4128 |εW(z)|4α=↓|4V(z)|g|≤a, |πwe have by di=erentiation|'
4133 {A6}|εW|β1|4α+↓|42W|β2z|4α+↓|43W|β3z|g2|4α+↓|1|1|¬O|4|¬O|4|¬
4133 O|1|1α=↓|4W|¬S(z)|4α=↓|4|≤aV(z)|g|≤a|gα_↓|g1V|¬S(z);|J!(6)|;
4134 {A6}|πtherefore|'{A6}|εW|¬S(z)V(z)|4α=↓|4|≤aW(z)V|¬S(z).|J!(
4135 7)|;{A6}|πIf we now equate the coe∃cients of
4143 |εz|gn|gα_↓|g1 |πin (7), we _nd that|'{A6}|ε|↔k|uc|)0|¬Ek|¬E
4149 n|)kW|βkV|βn|βα_↓|βk|4α=↓|4|≤a|↔k|uc|)0|¬Ek|¬En|)|4(n|4α_↓|4
4149 k)W|βkV|βn|βα_↓|βk,|J!(8)|;{A6}|πand this gives
4153 us a useful computational rule,|'{A6}|h|εW|βn|4|∂α=↓|4()|≤a|
4158 4α+↓|41|4α_↓|4n)V|β1W|βn|βα_↓|β1|4α+↓|4(2(|≤a|4α+↓|41)|4α_↓|
4158 4n)V|β2W|βn|βα_↓|β2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4n|≤aV|βn)/
4158 n,!!n|4α+↓|41.|E|n|;| W|βn|4|Lα=↓|4|↔k|uc|)1|¬Ek|¬En|)|4|↔a|
4159 ↔a|(|≤a|4α+↓|41|d2n|)|↔sk|4α_↓|41|↔sV|βkW|βn|βα_↓|βk>
4160 {A4}|Lα=↓|4{H12}({H10}(|≤a|4α+↓|41|4α_↓|4n)V|β1W|βn|βα_↓|β1|
4160 4α+↓|4(2(|≤a|4α+↓|41)|4α_↓|4n)V|β2W|βn|βα_↓|β2|4α+↓|1|1|¬O|4
4160 |¬O|4|¬O|1|1α+↓|4n|≤aV|βn{H12}){H10}/n,!!n|4|¬R|41.>
4161 {A2}(9)|?{A6}|H*?*?*?*?{U0}{H10L12M29}58320#Computer
folio 638 galley 6
4163 Programming!(A.-W./Knuth)!ch.!f. 638!g. 6D|'{A12}|π!|4|4|4|4
4166 The transformation of power series which is perhaps
4174 of greatest interest is called ``reversion of
4181 series.'' This problem is to solve the equation|'
4189 {A6}|εz|4α=↓|4t|4α+↓|4V|β2t|g2|4α+↓|4V|β3t|g3|4α+↓|4V|β4t|g4
4189 |4α+↓|1|1|¬O|4|¬O|4|¬O|J!(10)|;{A6}|πfor |εt,
4192 |πobtaining the coe∃cients of the power series|'
4199 {A6}|εt|4α=↓|4z|4α+↓|4W|β2z|g2|4α+↓|4W|β3z|g3|4α+↓|4W|β4z|g4
4199 |4α+↓|1|1|¬O|4|¬O|4|¬O|4.|J!(11)|;{A6}|πSeveral
4201 interesting ways to achieve such a reversion
4208 are known; we might say that the ``classical''
4216 method is one based on Lagrange's remarkable
4223 inversion formula [|εM|=1emoires Acad. royale
4228 des Sciences et Belles-Lettres de Berlin |≡2|≡4
4235 (1768), 251<326], |πwhich states that|'{A6}|εW|βn|4α=↓|4U|βn
4240 |βα_↓|β1/n,|;|πif|'|εU|β0|4α+↓|4U|β1t|4α+↓|4U|β2t|g2|4α+↓|1|
4242 1|¬O|4|¬O|4|¬O|1|1α=↓|4(1|4α+↓|4V|β2t|4α+↓|4V|β3t|g2|4α+↓|1|
4242 1|¬O|4|¬O|4|¬O)|gα_↓|gn.|J!(12)|;{A6}|πFor example,
4245 we have (|ε1|4α_↓|4t)|gα_↓|g5|4α=↓|4(|f4|d54|))|4α+↓|4(|f5|d
4247 54|))t|4α+↓|4(|f6|d54|))t|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|4;
4248 |πhence |εW|β5 |πin the reversion of |εz|4α=↓|4t|4α_↓|4t|g2
4255 |πis equal to (|f8|d54|))/5|4α=↓|414. This checks
4261 with the formulas for enumerating binary trees
4268 in Section 2.3.4.4.|'!|4|4|4|4Relation (12) shows
4274 that we can revert the series (10) if we compute
4284 |ε(1|4α+↓|4V|β2t|4α+↓|4V|β3t|g2|4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|
4284 gn |πfor |εn|4α=↓|41, 2, 3,|4.|4.|4.|4. |πA straightforward
4291 application of this idea would lead to an oλ-line
4300 power-series algorithm which uses approximately
4305 |εN|g3/2 |πmultiplications to _nd |εN |πcoe∃cients,
4311 but Eq. (9) makes it possible to work with onl
4321 y the _rst |εn |πcoe∃cients of |ε(1|4α+↓|4V|β2t|4α+↓|4V|β3t|
4327 g2|4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|gn, |πobtaining
4329 an on-line algorithm which has only about |εN|g3/6
4337 |πmultiplications.|'{A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡h|≡m
4339 |≡L (|εLagrangian power-series reversion). |πThis
4344 on-line algorithm inputs the value of |εV|βn
4351 |πin (10) and outputs the value of |εW|βn |πin
4360 (11), for |εn|4α=↓|42, 3, 4,|4.|4.|4.|4,|4N.
4365 |π(The number |εN |πneed not be speci_ed in advance;
4374 some other termination condition may be substituted.)|'
4381 {A6}{I1.8H}|≡L|≡1|≡.|9[Initialize.] Set |εn|4|¬L|41,
4384 U|β0|4|¬L|41. (|πDuring the course of this algorithm,
4391 we will have|'{A6}!!{H12}({H10}1|4α+↓|4V|β2t|4α+↓|4V|β3t|g2|
4394 4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|gn|4α=↓|4U|β0|4α+↓|4U|β1t|4α+↓|1
4394 |1|¬O|4|¬O|4|¬O|1|1α+↓|4U|βn|βα_↓|β1t|gn|gα_↓|g1|4α+↓|4O(t|g
4394 n).{H12}){H10}|;{A3}(13)|?{A6}|π|≡L|≡2|≡.|9[Input
4397 |εV|βn.] |πIncrease |εn |πby 1. If |εn|4|¬Q|4N,
4404 |πthe algorithm terminates; otherwise input the
4410 next coe∃cient, |εV|βn.|'{A3}|≡L|≡3|≡.|9[|πdivide.]
4414 Set |εU|βk|4|¬L|4U|βk|4α_↓|4U|βk|βα_↓|β1V|β2|4α_↓|1|1|¬O|4|¬
4415 O|4|¬O|1|1α_↓|4U|β1V|βk|4α_↓|4V|βk|βα+↓|β1, |πfor
4417 |εk|4α=↓|41, 2,|4.|4.|4.|4,|4n|4α_↓|42 (|πin
4420 this order); then set|'{A6}!!|εU|βn|βα_↓|β1|4|¬L|4|→α_↓2U|βn
4424 |βα_↓|β2V|β2|4α_↓|43U|βn|βα_↓|β3V|β3|4α_↓|1|1|¬O|4|¬O|4|¬O|1
4424 |1α_↓|4(n|4α_↓|41)U|β1V|βn|βα_↓|β1|4α_↓|4nV|βn|βα_↓|β1.|;
4425 {A6}!!|π{H12}({H10}We have thereby divided |εU(z)
4430 |πby |εV(z)/z; |πcf. (3) and (9).{H12})|'{H10}{A3}|≡L|≡4|≡.|
4436 9[Output |εW|βn.] |πOutput |εU|βn|βα_↓|β1/n (|πwhich
4441 is |εW|βn) |πand return to L2.|'{IC}{H9}|≡F|≡i|≡g|≡.
4448 |≡1|≡6|≡.|9|4Power-series reversion by algorithm
4452 L.|;{A6}{H10}When applied to the example |εz|4α=↓|4t|4α_↓|4t
4458 |g2, |πthe computation in Algorithm L is|'|∂!!!|∂!!!|∂!!!|∂!
4465 !∂!|∂!!!|∂!!!|∂!!!|∂!!!|∂|E|;|>|εn|;V|βn|;U|β0|;
4470 U|β1|;U|β2|;U|β3|;U|β4|;W|βn|;>{A2}|>1|;1|;1|;
4480 |;|;|;|;|9|11|;>|>2|;|→α_↓1|4|4|4|4|;1|;1|;|;
4492 |;|;1|;>|>3|;0|;1|;3|;|9|16|;|;|;|9|12|;>|>4|;
4508 0|;1|;4|;10|;20|;|;|9|15|;>|>5|;0|;1|;5|;15|;
4522 35|;70|;14|;>{A6}|πExercise 8 shows a slight
4531 modi_cation of algorithm L will solve a considerably
4539 more general problem with only a little more
4547 e=ort.|'!|4|4|4|4Let us now consider solving
4553 the equation|'{A6}|εU|β1z|4α+↓|4U|β2z|g2|4α+↓|4U|β3z|g3|4α+↓
4555 |1|1|¬O|4|¬O|4|¬O|1|1α=↓|4t|4α+↓|4V|β2t|g2|4α+↓|4V|β3t|g3|4α
4555 +↓|1|1|¬O|4|¬O|4|¬O|J!(14)|;{A6}|πfor |εt, |πobtaining
4559 the coe∃cients of the power series|'{A6}|εt|4α=↓|4W|β1z|4α+↓
4565 |4W|β2z|g2|4α+↓|4W|β3z|g3|4α+↓|4W|β4z|g4|4α+↓|1|1|¬O|4|¬O|4|
4565 ¬O|4.|J!(15)|;{A6}Eq. (10) is the special case
4572 |εU|β1|4α=↓|41, U|β2|4α=↓|4U|β3|4α=↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓
4573 |40. |πIf |εU|β1|4|=|↔6α=↓|40, |πwe may assume
4579 that |εU|β1|4α=↓|41, |πif we replace |εz |πby
4586 |ε(U|β1z); |πbut we shall consider the general
4593 equation (14), since |εU|β1 |πmight equal zero.|'
4600 {A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t|≡m |≡T (|εGeneral
4603 power-series reversion). |πThis on-line algorithm
4608 inputs the values of |εU|βn |πand |εV|βn |πin
4616 (14) and outputs the value of |εW|βn |πin (15),
4625 for |εn|4α=↓|41, 2, 3,|4.|4.|4.|4,|4N. |πAn auxiliary
4631 matrix |εT|βm|βn, 1|4|¬E|4m|4|¬E|4n|4|¬E|4N,
4634 |πis used in the calculations.|'{A6}{I1.8H}|≡T|≡1|≡.|9[Initi
4639 alize.] Set |εn|4|¬L|41. |πLet the _rst two inputs
4647 (namely, |εU|β1 |πand |εV|β1) |πbe stored in
4654 |εT|β1|β1 |πand |εV|β1, |πrespectively. (We must
4660 have |εV|β1|4α=↓|41).|'{A3}|π|≡T|≡2|≡.|9[Output
4663 |εW|βn.] |πOutput the value of |εT|β1|βn (|πwhich
4670 is |εW|βn).|'|π|≡T|≡3|≡.|9[Input |εU|βn, V|βn.]
4675 |πIncrease |εn |πby 1. If |εn|4|¬Q|4N, |πthe
4682 algorithm terminates; otherwise store the next
4688 two inputs (namely |εU|βn |πand |εV|βn) |πin
4695 |εT|β1|βn |πand |εV|βn, |πrespectively.|'{A3}|≡T|≡4|≡.|9[Mul
4699 tiply.] Set|'{A6}!!|εT|βm|βn|4|¬L|4T|β1|β1T|βm|βα_↓|β1|β,|βn
4701 |βα_↓|β1|4α+↓|4T|β1|β2T|βm|βα_↓|β1|β,|βn|βα_↓|β2|4α+↓|1|1|¬O
4701 |4|¬O|4|¬O|1|1α+↓|4T|β1|β,|βn|βα_↓|βm|βα+↓|β1T|βm|βα_↓|β1|β,
4701 |βm|βα_↓|β1|;{A6}!!|πand |εT|β1|βn|4|¬L|4T|β1|βn|4α_↓|4V|βmT
4703 |βm|βn, |πfor |ε2|4|¬E|4m|4|¬E|4n. |π(After this
4708 step we have the conditions|'{A6}|εt|gm|4α=↓|4T|βm|βmz|gm|4α
4713 +↓|4T|βm|β,|βm|βα+↓|β1z|gm|gα+↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1
4713 α+↓|4T|βm|βnz|gn|4α+↓|4O(z|gn|gα+↓|g1),!!1|4|¬E|4m|4|¬E|4n.|
4713 ;{A2}(16)|?{A6}|π!!It is easy to verify (16)
4721 by induction for |εm|4|¬R|42, |πand when |εm|4α=↓|41,
4728 |πwe have |εU|βn|4α=↓|4T|β1|βn|4α+↓|4V|β2T|β2|βn|4α+↓|1|1|¬O
4730 |4|¬O|4|¬O|1|1α+↓|4V|βnT|βn|βn |πby (14) and
4734 (19).) Return to step T2.|'{IC}{A12}!|4|4|4|4Equation
4740 (16) explains the mechanism of this algorithm,
4747 which is due to Henry C. Thacher, Jr. [|εCACM
4756 |≡9 (1966), 10<11]. |πThe running time is essentially
4764 the same as Algorithm L, but considerably more
4772 storage space is required. An example of this
folio 643 galley 7
4780 algorithm is worked in exercise 9.|'|H*?*?*?{U0}{H10L12M29}5832
4786 0#Computer Programming!(A.-W./Knuth)!ch. 4!f.
4789 643!g. 7D|'{A12}!|4|4|4|4Still another approach
4794 to power series reversion has been proposed by
4802 R. P. Brent and H. T. Kung [|εAnalytic computational
4811 complexity, |πed. by Traub (New York: Academic
4818 Press, 1975), 000<000], who observed that standard
4825 iterative procedures used to _nd roots of equations
4833 over the real numbers can usefully be applied
4841 also to equations over power series. In particular,
4849 consider Newton's method for computing approximations
4855 to a real number |εt |πsuch that |εf|1(t)|4α=↓|40,
4863 |πgiven a function |εf |πthat is well-behaved
4870 near |εt: |πIf |εx |πis a good approximation
4878 to |εT, |πthen |ε|≤f(x)|4α=↓|4x|4α_↓|4f|1(x)/f|¬S(x)
4882 |πwill be even better, for it we write |εx|4α=↓|4t|4α+↓|4|≤o
4890 |πwe have |εf|1(x)|4α=↓|4f|1(t)|4α+↓|4|≤of|¬S(t)|4α+↓|4O(|≤
4893 o|g2), f|¬S(x)|4α=↓|4f|¬S(t)|4α+↓|4O(|≤o), |πand
4896 |ε|≤'(x)|4α=↓|4t|4α+↓|4|≤o|4α_↓|4{H12}({H10}0|4α+↓|4|≤of|¬S(
4896 t)|4α+↓|4O(|≤o|g2){H12}){H10}/{H12}({H10}f|¬S(t)|4α+↓|4O(|≤o
4896 ){H12}){H10}|4α=↓|4t|4α+↓|4O(|≤o|g2). |πApplying
4898 this idea to power series, let |εf|1(x)|4α=↓|4V(x)|4α_↓|4U(z
4904 ), |πwhere |εU |πand |εV |πare the pwer series
4913 in Eq. (14). We wish to lnd the power series
4923 |εt |πin |εz |πsuch that |εf|1(t)|4α=↓|40. |πLet
4930 |εx|4α=↓|4W|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|4|4α+↓|4W|βn|βα_↓|β1z|
4930 gn|gα_↓|g1|4α=↓|4t|4α+↓|4O(z|gn) |πbe an ``approximation''
4934 to |εt |πof order |εn; |πthen |ε|≤'(x)|4α=↓|4x|4α_↓|4f|1(x)/
4940 f|¬S(x) |πwill be an approximation of order |ε2n,
4948 |πsince the assumptions of Newton's method hold
4955 for this |εf |πand |εt.|'!|4|4|4|4|πWe therefore
4962 can use the following procedure:|'{A12}|≡A|≡l|≡g|≡o|≡r|≡i|≡t
4967 |≡h|≡m |≡N |ε(General power series reversion
4973 by Newton's method).|9|4|πThis ``semi-on-line``
4977 algorithm inputs the values of |εU|βn |πand |εV|βn
4985 in (14) |πfor |ε2|gk|4|¬E|4n|4|¬Q|42|gk|gα+↓|g1
4989 |πand then outputs the values of |εW|βn |πin
4997 (15) for |ε2|gk|4|¬E|4n|4|¬Q|42|gk|gα+↓|g1, |πthereby
5001 producing its answers in batches of |ε2|gk |πat
5009 a time, for |εk|4α=↓|40, 1, 2,|4.|4.|4.|4,|4K.|'
5015 {A6}{I1.8H}|π|≡N|≡1|≡.|9[Initialize.] Set |εN|4|¬L|41.
5018 (|πWe will have |εN|4α=↓|42|gk.) |πInput the
5024 _rst coe∃cients |εU|β1 |πand |εV|β1 |π(where
5030 |εV|β1|4α=↓|41), |πand set |εW|β1|4|¬L|4U|β1.|'
5034 {A3}|π|≡N|≡2|≡.|9[Output.] Output |εW|βn |πfor
5038 |εN|4|¬E|4n|4|¬Q|42N.|'{A3}|π|≡N|≡3|≡.|9[Input.]
5040 Set |εN|4|¬L|42N. |πIf |εN|4|¬Q|42|gK, |πthe
5045 algorithm terminates; otherwise input the values
5051 |εU|βn |πand |εV|βn |πfor |εN|4|¬E|4n|4|¬W|42N.|'
5056 {A3}|π|≡N|≡4|≡.|9[Newtonian step.] Use an algorithm
5061 for power series composition (see exercise 11)
5068 to evaluate the coe∃cients |εQ|βj, R|βj (0|4|¬E|4j|4|¬W|4N)
5075 |πin the power series|'{A6}|h|εV|¬S(W|β1z|4α+↓|1|1|¬O|4|¬O|4
5079 |¬O|1|1α+↓|4W|βN|βα_↓|β1z|gN|gα_↓|g1)|4|∂α=↓|4Q|β0|4α+↓|4Q|β
5079 1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4Q|βN|βα_↓|β1z|gN|gα_↓|g1|4α
5079 +↓|4O(z|gN),|E|n|;!!U|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4U|β2
5080 |βN|βα_↓|β1z|g2|gN|gα_↓|g1|4α_↓|4V(W|β1z|4α+↓|1|1|¬O|4|¬O|4|
5080 ¬O|1α+↓|4W|βN|βα_↓|β1z|gN|gα_↓|g1)|'{A4}α=↓|4R|β0z|gN|4α+↓|4
5081 R|β1z|gN|gα+↓|g1|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4R|βN|βα_↓|β1z
5081 |g2|gN|gα_↓|g1|4α+↓|4O(z|g2|gN),>{A6}V|¬S(W|β1z|4α+↓|1|1|¬O|
5082 4|¬O|4|¬O|1|1α+↓|4W|βN|βα_↓|β1z|gN|gα_↓|g1)|4α=↓|4Q|β0|4α+↓|
5082 4Q|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4Q|βN|βα_↓|β1z|gN|gα_↓|g
5082 1|4α+↓|40(z|gN),>{A6}!!|πwhere |εV(x)|4α=↓|4x|4α+↓|4V|β2x|g2
5084 |4α+↓|1|1|¬O|4|¬O|4|¬O |πand |εV|¬S(x)|4α=↓|41|4α+↓|42V|β2x|
5086 4α+↓|1|1|¬O|4|¬O|4|¬O|4. |πThen set |εW|βN,|4.|4.|4.|4,|4W|β
5089 2|βN|βα_↓|β1 |πto the coe∃cients in the power
5096 series|'{A6}|ε!!|(R|β0|4α+↓|4R|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1
5097 α+↓|4R|βN|βα_↓|β1z|gN|gα_↓|g1|d2Q|β0|4α+↓|4Q|β1z|4α+↓|1|1|¬O
5097 |4|¬O|4|¬O|1|1α+↓|4Q|βN|βα_↓|β1z|gN|gα_↓|g1|)|4α=↓|4W|βN|4α+
5097 ↓|4W|βN|βα+↓|β1z|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α+↓|4W|β2|βN|βα_↓|
5097 β1z|gN|gα_↓|g1|4α+↓|4O(z|gN)|;{A6}!!|πand return
5100 to step N2.|'{A6}{IC}!|4|4|4|4The running time
5106 for this algorithm to obtain the coe∃cients up
5114 to |εN|4α=↓|42|gK |πis |εT(N), |πwhere|'{A6}|εT(2N)|4α=↓|4T(
5119 N)|4α+↓|4(|πtime|4to|4do|4step|4N4|4α+↓|4|εO(N).|J!(17)|;
5120 {A6}|πStraightforward algorithms for composition
5124 and division in step N4 will take order |εN|g3
5133 |πsteps, so Algorithm N will run slower than
5141 Algorithm T. However, Brent and Kung have found
5149 a way to do the required composition of power
5158 series with |εO(N|4|πlog|4|εN)|g3|g/|g2 |πarithmetic
5162 operations, and exercise 6 gives an even faster
5170 algorithm for division; hence (17) shows that
5177 power series reversion can be achieved by doing
5185 only |εO(N|4|πlog|4|εN)|g3|g/|g2 |πoperations
5188 as |εN|4|¬M|4|¬X. |π(On the other hand the constant
5196 of proportionality is such that |εN |πmust be
5204 really large before Algorithms L and T lose out
5213 to this ``high-speed'' method.)|'|εHistorical
5218 note|*/: |\|πJ. N. Bramhall and M. A. Chapple
5226 published the _rst |εO(n|g3) |πmethod for power
5233 series reversion [|εCACM |≡4 (1961), 317<318,
5239 503]; |πit was an o=-line algorithm whose running
5247 time was approximately the same as Algorithms
5254 L and T.|'{A24}|∨E|∨X|∨E|∨R|∨C|∨I|∨S|∨E|∨S|'{A12}{H9L11M29}|
5258 9|1|≡1|≡.|9[|εM|*/|↔O|↔c|\] |πThe text explains
5262 how to divide |εU(z) |πby |εV(z) |πwhen |εV|β0|4|=|↔6α=↓|40;
5269 |πhow should the division be done when |εV|β0|4α=↓|40?|'
5278 {A3}|9|1|≡2|≡.|9[|*/|↔P|↔c|\] |πIf the coe∃cient
5282 of |εU(z) |πand |εV(z) |πare integers and |εV|β0|4|=|↔6α=↓|4
5289 0, |πa recurrence relation for the integers |εV|urnα+↓1|)0|)
5296 W|βn, |πwhere |εW|βn |πis de_ned by (3). How
5304 would you use this for power series division?|'
5312 {A3}|9|1|≡3|≡.|9[|εM|*/|↔O|↔C|\] |πDoes formula
5315 (9) give the right results when |ε|≤a|4α=↓|40?
5322 |πWhen |ε|≤a|4α=↓|41?|'{A3}|9|1|≡4|≡.|9[HM|*/|↔P|↔L|\]
5325 |πShow that simple modi_cations of (9) can be
5333 used to calculate |εe|gV|g(|gz|g) |πand ln{H12}({H9}1|4α+↓|4
5338 |εV(z){H12}){H9}, |πwhen |εV(z)|4α=↓|4V|β1z|4α+↓|4V|β2z|g2|4
5340 α+↓|1|1|¬O|4|¬O|4|¬O|4.|'{A3}|9|1|≡5|≡.|9[M|*/|↔c|↔c|\]
5342 |πWhat happens when a power series is reverted
5350 twice; i.e., if the output of algorithm R or
5359 S is reverted again?|'{A3}|9|1|≡6|≡.|9[|εM|*/|↔P|↔O|\]
5364 |π(H. T. Kung.) Apply Newton's method to the
5372 computation of |εW(z)|4α=↓|41/V(z), |πwhen |εV(0)|4|=|↔6α=↓|
5376 40, |πby _nding the power-series root of |εf|1(x)|4α=↓|4x|gα
5383 _↓|g1|4α_↓|4V(z).|'{A3}|9|1|≡7|≡.|9[M|*/|↔P|↔L|\]
5385 |πUse Lagrange's inversion formula (12) to _nd
5392 a simple expression for the coe∃cient |εW|βn
5399 |πin the reversion of |εz|4α=↓|4t|4α_↓|4t|gm.|'
5404 {A3}|9|1|≡8|≡.|9[M|*/|↔P|↔C|\] |πLagrange's inversion
5407 formula can be generalized as follows: If |εW(z)|4α=↓|4W|β1z
5414 |4α+↓|4W|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4G|β1t|4α+↓|4G|
5414 β2t|g2|4α+↓|4G|β3t|g3|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4G(t),
5415 |πwhere |εz |πand |εt |πare related by Eq. (10),
5424 then |εW|βn|4α=↓|4U|βn|βα_↓|β1/n |πwhere|'{A6}|εU|β0|4α+↓|4U
5427 |β1z|4α+↓|4U|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|4(G|β1|4α+↓
5427 |42G|β2z|4α+↓|43G|β3z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O)(1|4α+↓|4V|β2
5427 z|4α+↓|4V|β3z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O)|gα_↓|gn.|;
5428 {A6}|π(Equation (12) is the speical case |εG|β1|4α=↓|41,
5435 G|β2|4α=↓|4G|β3|4α=↓|1|1|¬O|4|¬O|4|¬O|1|1α=↓|40.
5436 |πThis equation can be proved, for example, by
5444 using tree-enumeration formulas as in exercise
5450 2.3.4.4<33.)|'!!|1|1Ecxtend algorithm L so that
5456 it obtains the coe∃cients |εW|β1, W|β2,|4.|4.|4.|4,
5462 |πin this more general situation, without substantially
5469 increasing its running time.|'{A3}|9|1|9|1|≡9|≡.|9[|ε|*/|↔O|↔
5473 O|\] |πFind the values of |εT|βm|βn |πcomputed
5480 by Algorithm T as it determines the _rst _ve
5489 coe∃cients in the reversion of |εz|4α=↓|4t|4α_↓|4t|g2.|'
5495 {A3}|≡1|≡0|≡.|9[M|*/|↔P|↔c|\] |πgiven that |εy|4α=↓|4x|g|≤a|4
5498 α+↓|4a|β1x|ur|≤aα+↓2|)|)|4α+↓|1|1|¬O|4|¬O|4|¬O|4,
5499 |≤a|4|=|↔6α=↓|40, |πshow how to compute the coe∃cients
5506 in the expansion |εx|4α=↓|4y|g1|g/|g|≤a|4α+↓|4b|β2y|g2|g/|g|
5509 ≤a|4α+↓|4b|β3y|g3|g/|g|≤a|4α+↓|1|1|¬O|4|¬O|4|¬O|4.|'
5510 {A3}|≡1|≡1|≡.|9[M|*/|↔P|↔C|\] |πLet|'{A6}|εU(z)|4α=↓|4U|β0|4α
5512 +↓|4U|β1z|4α+↓|4U|β2z|g2|4α+↓|1|1|¬O|4|¬O|4|¬O!|πand!|εV(z)|
5512 4α=↓|4V|β1z|4α+↓|4V|β2z|g2|4α+↓|4V|β3z|g3|4α+↓|1|1|¬O|4|¬O|4
5512 |¬O|4;|;{A6}|πdesign an algorithm which computes
5518 the _rst |εN |πcoe∃cients of |εU{H12}({H9}V(z){H12}){H9}.|'
5524 {A3}|≡1|≡2|≡.|9[M|*/|↔P|↔c|\] |πFind a connection
5528 between polynomial division and power-series
5533 division: Given polynomials |εu(x) |πand |εv(x)
5539 |πof respective degrees |εm |πand |εn |πover
5546 a _eld, show how to _nd the polynomials |εq(x),
5555 r(x) |πsuch that |εu(x)|4α=↓|4q(x)v(x)|4α+↓|4r(x),
5559 |πdeg|ε(r)|4|¬W|4n, |πusing only operations on
5564 power series.|'{A24}|}|O|*/{H8L9M29}And it shall
5569 be,|?when thou hast made an end of reading this
5579 book,|?that thou shalt bind a stone to it,|?and
5589 cast it int*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!*!
5591